1337C - Linova and Kingdom - CodeForces Solution

#include<bits/stdc++.h>

using namespace std;


typedef long long ll;
typedef long int li;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<vector<int>> vvi;
typedef pair<int,int> pii;
//typedef long long int;

#define endl "\n"
#define f(i,a,b) for(int i=a;i<=(b);i++)
#define r(i,a,b) for(int i=a;i>=(b);i--)
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define mid(s,l) (s+(l-s)/2)
#define umap unordered_map
#define pb push_back
#define mp make_pair
//#define int long long

//const int INF = int(1e9);
//const int MOD = int(1e9) + 7;
//const ld EPS = 1e-18;
//const ld PI = acos(-1.0); 

const int N = 2e5 + 3;
vector<vector<int>> adj(N);
vector<int> con;
vector<int> depth(N);
int dfs(int vert , int par){
	depth[vert] = depth[par] + 1;
	int val = 0;
	for(auto child : adj[vert]){
		if(child == par) continue;
		val += dfs(child , vert);
	}
	con.pb(depth[vert] - 1 - val);
	//cout << vert << ' ' << val << ' ' << depth[vert] - 1 - val << endl;
	return val + 1;	
}

void GG()
{
	adj.clear();
	con.clear();
	depth.clear();
	int n;
	cin >> n;
	adj.resize(n + 3);
	depth.resize(n + 3);
	int k;
	cin >> k;
	for(int i = 2; i <= n; i++){
		int u , v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	dfs(1 , 0);
	sort(all(con) , greater<int>());
	ll tot = 0;
	for(int i = 0; i < k; i++)
		tot += (ll) con[i];
	cout << tot << endl;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int ttc=1;
	//cin>>ttc;
	//int cnt=0;
	while(ttc--)
	{
		//cout<<"Case "<<++cnt<<": ";
		GG();
	}
}